package com.leetcode.easy;

import com.leetcode.entity.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Classname HasCycle
 * @Description 判断链表是否有环
 * @Date 2020/9/23 10:53
 * @Created by zfl
 */
public class HasCycle {

    /**
     * @param head
     * @return
     * 执行用时：5 ms, 在所有 Java 提交中击败了16.77%的用户
     * 内存消耗：39.3 MB, 在所有 Java 提交中击败了20.96%的用户
     */
    public static boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }

        //ListNode slow = head;
        Set<ListNode> set = new HashSet<>();
        ListNode fast = head;
        set.add(fast);
        while (fast != null) {
            fast = fast.next;
            if(!set.contains(fast)) {
                set.add(fast);
            }else {
                return true;
            }
        }
        return false;
    }

    /**
     * @param head
     * @return
     * 注意边界问题
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了73.01%的用户
     * 时间复杂度：O(n);空间复杂度O(1).
     */
    public static boolean hasCycle2(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
            if(fast == null) {
                return false;
            }
        }
        return false;
    }

    public static boolean hasCycle3(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != slow) {
            if(fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}
